Perl Cookbook, 2nd Edition by Tom Christiansen and Nathan Torkington

Author:Tom Christiansen and Nathan Torkington
Language: eng
Format: mobi
Tags: COMPUTERS / Programming Languages / JavaScript
Publisher: O’Reilly Media
Published: 2009-02-08T16:00:00+00:00

See Also

The algorithms in this recipe derive in part from pages 206-207 of Introduction to Algorithms, by Cormen, Leiserson, and Rivest (MIT Press/McGraw-Hill). See also Recipe 13.13; the section on “Garbage Collection, Circular References, and Weak References” in Chapter 8 of Programming Perl; the documentation for the standard Devel::Peek and Scalar::Util modules

11.16. Program: Outlines

Outlines are a simple (and thus popular) way of structuring data. The hierarchy of detail implied by an outline maps naturally to our top-down way of thinking about the world. The only problem is that it’s not obvious how to represent outlined data as a Perl data structure.

Take, for example, this simple outline of some musical genres:

Alternative .Punk ..Emo ..Folk Punk .Goth ..Goth Rock ..Glam Goth Country .Old Time .Bluegrass .Big Hats Rock .80s ..Big Hair ..New Wave .60s ..British ..American

Here we use a period to indicate a subgroup. There are many different formats in which that outline could be output. For example, you might write the genres out in full:

Alternative Alternative - Punk Alternative - Punk - Emo Alternative - Punk - Folk Punk Alternative - Goth ...

You might number the sections:

1 Alternative 1.1 Punk 1.1.1 Emo 1.1.2 Folk Punk 1.2 Goth ...

or alphabetize:

Alternative Alternative - Goth Alternative - Goth - Glam Goth Alternative - Goth - Goth Rock Alternative - Punk Alternative - Punk - Emo ...

or show inheritance:

Alternative Punk - Alternative Emo - Punk - Alternative Folk Punk - Punk - Alternative Goth - Alternative Goth Rock - Goth - Alternative ...

These transformations are all much easier than it might seem. The trick is to represent the levels of the hierarchy as elements in an array. For example, you’d represent the third entry in the sample outline as:

@array = ("Alternative", "Goth", "Glam Goth");

Now reformatting the entry is trivial. There’s an elegant way to parse the input file to get this array representation:

while (<FH>) { chomp; $tag[$in = s/\G\.//g] = $_; # do something with @tag[0..$in] }

The substitution deletes leading periods from the current entry, returning how many it deleted. This number indicates the indentation level of the current entry.

Alphabetizing is now simple using the Unix sort program:

$ISA = "-"; open(STDOUT, "|sort -b -t'$ISA' -df"); while (<DATA>) { chomp; $tag[$in = s/\G\.//g] = $_; print join(" $ISA ", @tag[0 .. $in]); } close STDOUT; _ _END_ _ Alternative .Punk ..Emo ..Folk Punk .Goth

Numbering the outline is equally simple:

while (<DATA>) { chomp; $count[$in = s/\G\.//g]++; delete @count[($in+1) .. $#count]; print join(".", @count), " $_"; } _ _END_ _ Alternative .Punk ..Emo ..Folk Punk .Goth ..Goth Rock

Notice that renumbering is our only application where we’ve deleted elements from the array. This is because we’re not keeping names of hierarchy levels in the array; now we’re keeping counts. When we go up a level (e.g., from three levels down to a new second-level heading), we reset the counter on the old level.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.